package com.example.leetcode.leetcode;

/**
 * @author zht
 * @date 2021/1/13 9:31
 */
public class Solution647 {

//    public static int countSubstrings(String s) {
//        int ans = 0;
//        for (int i = 0; i < s.length(); i++) {
//            for (int j = i; j <s.length(); j++) {
//                if (check(s.substring(i,j+1))){
//                    ans++;
//                }
//            }
//        }
//        return ans;
//    }
//    public static boolean check(String s){
//        if(s.length()==1){
//            return true;
//        }
//        int left,right;
//        int middle = (s.length()-1)/2;
//        if(s.length()%2==0){
//            left=middle;
//            right=middle+1;
//        }else{
//            left=middle-1;
//            right=middle+1;
//        }
//
//        while(left>=0&&right<s.length()){
//            if(s.charAt(left)!=s.charAt(right)){
//                return false;
//            }
//            left--;
//            right++;
//        }
//        return true;
//    }



    public static int countSubstrings(String s) {
        int n = s.length();
        StringBuffer t = new StringBuffer("$#");
        // 添加间隔的#字符，是的所有的回文都是奇数长度的，这样不会改变结果
        for (int i = 0; i < n; ++i) {
            t.append(s.charAt(i));
            t.append('#');
        }
        n = t.length();
        t.append('!');

        int[] f = new int[n];
        // iMax为最右侧回文的中心点， rMax为最右侧回文的最有点
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; i++) {
            //初始化
            f[i] = i <= rMax ?Math.min(f[iMax*2-i],rMax-i+1):1;
            while(t.charAt(i-f[i])==t.charAt(i+f[i])){
                f[i]++;
            }
            if (i+f[i]-1>rMax){
                rMax = f[i]+i-1;
                iMax = i;
            }
            ans+= f[i]/2;
        }

        return ans;
    }

    public static void main(String[] args) {
        String s="abb";
        System.out.println(countSubstrings(s));
    }
}
